package com.zy.recursion;

import com.zy.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @description: 不同的二叉搜索树 II
 * @author: zhaoyi
 * @create: 2019-09-15 15:37
 * https://leetcode-cn.com/explore/orignial/card/recursion-i/260/conclusion/1233/
 **/

public class TreeNodeFind {

    /**
     * 重点思路
     * 左子树 < 根 < 右子树
     *  从序列 1 ..n 取出数字 i 并以它作为当前树的根节点。
     *  那么就有 i - 1 个元素可以用来构造左子树，而另外的 n - i 个元素可以用于构造右子树。
     *  最后我们将会得到 G(i - 1) 棵不同的左子树，以及 G(n - i) 棵不同的右子树，其中 G 为卡特兰数。
     *
     *  官方解答
     *  https://leetcode-cn.com/explore/orignial/card/recursion-i/260/conclusion/1234/
     * @param n
     * @return
     */
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return null;
        }
        return findTrees(1, n);
    }

    private List<TreeNode> findTrees(int start, int end) {
        List<TreeNode> trees = new LinkedList<TreeNode>();
        if (start > end) {
            trees.add(null);
            return trees;
        }

        for (int i = start; i <= end; i++) {
            List<TreeNode> left_trees = findTrees(start, i - 1);
            List<TreeNode> right_trees = findTrees(i + 1, end);
            for (TreeNode l : left_trees) {
                for (TreeNode r : right_trees) {
                    TreeNode current_tree = new TreeNode(i);
                    current_tree.left = l;
                    current_tree.right = r;
                    trees.add(current_tree);
                }
            }
        }
        return trees;
    }

}
